package leetCode.solution;

import java.util.PriorityQueue;

public class Solution905 {

	 // 已知n是正数
 	// 返回大于等于，且最接近n的，2的某次方的值
 	public static final int tableSizeFor2(int n) {
 		if(n==0) return 1;
 		if(n==1) return 1;
 		n-=1;
// 		if((n&(n-1))==0) return n;
 		int t = 0;
 		while(n!=0) {
 			t=n;
 			n-=n&(~n+1);
 		}
 		return 2*t;
 	}
 	
 	public static final int tableSizeFor1(int n) {
		n--;
		n |= n >>> 1;
		n |= n >>> 2;
		n |= n >>> 4;
		n |= n >>> 8;
		n |= n >>> 16;
		return (n < 0) ? 1 : n + 1;
	}

 	public static void main(String[] args) {
 		int count = 50000000;
 		int max = 23435645;
 		for(int i=0;i<count;i++) {
 			int n = (int)(Math.random()*max);
 			if(tableSizeFor2(n)!=tableSizeFor1(n)) {
 				System.out.println(n);
 				System.out.println(tableSizeFor1(n));
 				System.out.println(tableSizeFor2(n));
 			}
 		}
 		
 	}
}
